Some embodiments of the present disclosure are directed to an improved approach for implementing/generating an ordered sequence in a database system using multiple interleaved caches. More particularly, some embodiments disclosed herein are a method and system for generating ordered sequences using semaphore protected interleaved caches.
Overview of Latch Contention
In a modern database system for processing transactions (e.g., commercial transactions such as purchase orders, debits, credits, etc.) many users can use the system at the same time, and many users may have the same sorts of operations to perform. For example, if a user, say User A, desires to process a batch of purchase orders, he or she might want to assign each one of those purchase orders in the batch a unique number. And, it might be desired to assign those purchase orders a unique number within a contiguous sequence (e.g., PO-0001, PO-0002, PO-0003, etc.).
One technique is to assign a large range of contiguous numbers for all users to access and ‘check-out’ a contiguous sequence. For example, if User A desired to process a batch of say, 20 purchase orders, he or she might request a sequence comprising 20 contiguous numbers (e.g., 0001, 0002, 0003, . . . 0020). However a different user, say User B, might at the same time also desire to process a batch of purchase orders, and could at the same time request a sequence comprising 20 contiguous numbers. One legacy technique for ensuring that User A and User B do not receive the same sequence comprising 20 contiguous numbers is to enforce requests to be serialized. There are various techniques for serialization of requests, often involving serialization of requests using a flag or latch (or any implementation of a semaphore). In such a case for using a flag or latch, a first user (say User A) is granted access to the list of contiguous sequences, while any next users must wait. Then the first user is given the requested sequence (in this example, numbers 0001-0020), and the next waiting user's request is then processed. Given that the first user's request was satisfied (thus, the next available would be 0021) the first waiting user's request (e.g., a sequence of 20 contiguous numbers) can be satisfied by returning the sequence 0021, 0022, 0023 through 0040, and so on.
While use of the aforementioned flag or “sequence latch” is effective for serialization, in the case that there are a large number of users, there can be many users waiting for their turn to have their request satisfied, and the users can become ‘backed up’ as they contend for access to the sequence latch. In the case of modern database systems for processing a large number of transactions (e.g., transaction that need a sequence number), the waiting time can become as large a portion of time as the processing time. In fact, as the number of concurrent users increases and, as the number of requests for sequences increases, the portion of time spent in waiting can be larger than the remaining time needed to process the transaction.
Various implementations involving regimes of multiple latches, have been proposed, yet as the number of concurrent users increases and, as the processing power available to those concurrent users increases, the number of requests for sequences explodes, demanding new techniques to reduce or eliminate the portion of time spent in waiting for a sequence value to be satisfied and to reduce or eliminate the absolute amount of time spent waiting for a sequence value to be satisfied.
Moreover, the aforementioned technologies do not have the capabilities to perform generating ordered sequences using interleaved caches that reduce latency while still strictly observing the desired ordering.
Therefore, there is a need for an improved approach for implementing generating ordered sequences using semaphore protected interleaved caches.